package main

import (
	"fmt"
	"time"
)

func main() {
	head := new(Node)
	Add(head, 1)
	Add(head, 2)
	Add(head, 3)
	Add(head, 4)
	Add(head, 5)
	Add(head, 6)
	fmt.Println(head.IsCycle())

	head.Range()
	//newHead := ReverseLinked(head)
	//fmt.Println()
	//newHead.Range()

}

// 链表结构
type Node struct {
	Value int
	Next  *Node
	Prev  *Node
}

func ReverseLinked(head *Node) *Node {
	cur, prev := head.Next, (*Node)(nil)
	for cur != nil {
		cur.Next, prev, cur = prev, cur, cur.Next
	}

	head.Next, prev.Prev = prev, head

	return head
}

func Add(head *Node, v int) *Node {
	cur := head

	for cur.Next != nil {
		cur = cur.Next
	}

	cur.Next = &Node{
		Prev:  cur,
		Value: v,
	}

	// 刻意给链表加个环
	if v == 6 {
		cur.Next.Next = cur.Prev.Prev
	}

	return head
}

func (head *Node) Range() {
	cur := head
	for cur.Next != nil {
		cur = cur.Next
		fmt.Print(cur.Value, " ")
		time.Sleep(time.Millisecond * 200)
	}
}

// 判断链表是否有环
func (head *Node) IsCycle() bool {
	tmp := make(map[*Node]struct{})
	cur := head.Next

	for cur != nil {
		_, ok := tmp[cur]
		if ok {
			return true
		}
		tmp[cur] = struct{}{}
		cur = cur.Next
	}
	return false
}
